class Solution {
public:
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int> > inIndeg(row,vector<int>(col,0));
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                for(int k = 0;k < 4;k++){
                    int x = i + dirs[k][0];
                    int y = j + dirs[k][1];
                    if(x >= 0 && x < row && y >= 0 && y < col && matrix[x][y] < matrix[i][j]){
                        inIndeg[i][j]++;
                    }
                }
            }    
        }
        
        queue<pair<int,int> > qe;
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                if(inIndeg[i][j] == 0){
                    qe.push({i,j});
                }
            }
        }
        
        int ret = 0;
        while(!qe.empty()){
            ret++;
            int size = qe.size();
          for(int i = 0;i < size;i++){
              
            auto& w = qe.front();
            int x = w.first;
            int y = w.second;
            qe.pop();
            for(int k = 0;k < 4;k++){
                int xx = x + dirs[k][0];
                int yy = y + dirs[k][1];
                if(xx >= 0 && xx < row && yy >= 0 && yy < col && matrix[xx][yy] > matrix[x][y]){
                    inIndeg[xx][yy]--;
                    if(inIndeg[xx][yy] == 0){
                        qe.push({xx,yy});
                    }
                }
            }
          }
        }
        return ret;
    }
};
